package LearnAlgorithm.j_动态规划and贪心算法;

import java.util.ArrayList;
import java.util.Scanner;

/*
求最大公共子序列问题
可以隔位选取子序列，但是必须顺序从左到右
in
AB34C
A1BC2 

out
ABC

*/
public class i最长公共子序列LCSbyDFS {
	public static void main(String[] args) {
		i最长公共子序列LCSbyDFS test = new i最长公共子序列LCSbyDFS();
		test.useDFS();
	}
	
	/**
	 * 前置方法
	 */
	public void useDFS() {
		Scanner scanner = new Scanner(System.in);
		String s1 = scanner.next();
		String s2 = scanner.next();
		ArrayList<Character> res = DFS(s1, s2);
		System.out.println(res);
	}
	
	/**
	 * 双重循环的内循环套递归
	 * @param s1
	 * @param s2
	 * @return
	 */
	public ArrayList<Character> DFS(String s1, String s2) {
		int len1 = s1.length();
		int len2 = s2.length();
		ArrayList<Character> res = new ArrayList<Character>();//“历史最长公共子序列”
		for (int i = 0; i < len1; i++) {//求以i字符开头的公共子序列
			ArrayList<Character> temp = new ArrayList<Character>();
			for (int j = 0; j < len2; j++) {//和s2的每个字符比较
				if (s1.charAt(i) == s2.charAt(j)) {//发现了相同字符A
					temp.add(s1.charAt(i));//运用老板思想；我只把A压入临时集合，剩下的“未知长度”的“公共子序列”用递归的方式寻找
					temp.addAll(DFS(s1.substring(i + 1), s2.substring(j + 1)));//递归的方式寻找；其实这递归可以改成第三重循环，但没必要
					break;//找到了以i字符开头的公共子序列B后，直接结束内for循环
				}
			}
			if (temp.size() > res.size()) {//判断这B比“历史最长公共子序列”长不长
				res = temp;//长，就更新“历史最长公共子序列”
			}
		}
		return res;
	}
}
